package sort.test3_31;


import java.util.Arrays;

//  CKG TODO 2023/3/31:   基数排序　　　   第一步：找到最大数值　　第二步：按照从个位十位　到百位　
//    //   将数组中的元素值一次排序到　十个桶中　　排序完数组就是按照顺序排列的
public class RadixSort {
    public  void  sort(int[] nums){
        if (nums.length==0){
            return;
        }
        int max=Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            max=Math.max(max,nums[i]);
        }
        for (int exp = 1; max/exp >0 ; exp*=10) {
            adjust(nums,exp);
        }


    }

    public  void   adjust(int[] nums,int  exp){
        int length = nums.length;
        int[] countArray = new int[10];
        int[] output = new int[length];
        for (int i = 0; i < nums.length; i++) {
            countArray[(nums[i]/exp)%10]++;
        }
        for (int i = 1; i < countArray.length; i++) {
            countArray[i]+=countArray[i-1];
        }

        //  CKG TODO 2023/3/31: 这一块的逻辑还是没有搞懂
        for (int i = nums.length - 1; i >= 0; i--) {
//        for (int i = 0; i < nums.length; i++) {
            output[countArray[(nums[i]/exp)%10]-1]= nums[i];
            countArray[(nums[i]/exp)%10]--;
        }

        for (int i = 0; i < length; i++) {
            nums[i]=output[i];
        }
        countArray=null;
        output=null;

    }

    public static void main(String[] args) {
        RadixSort radixSort = new RadixSort();
        int arr[] = {10,5,11,6};
        radixSort.sort(arr);
        System.out.println(Arrays.toString(arr));

    }





}
